package 数组;

import java.util.Arrays;
import java.util.Random;

/**
 * Author: Zhang Dongwei
 * Date: 2022/4/1 12:35
 * 给你一个整数数组 nums，请你将该数组升序排列。
 */
public class 排序数组_912_quicksort {
    public static void main(String[] args) {
        int[] nums = new int[] {5,2,3,1};
        System.out.println(Arrays.toString(nums));
        int[] res = sortArray(nums);
        System.out.println(Arrays.toString(res));
    }

    public static int[] sortArray(int[] nums) {
        quicksort(nums, 0, nums.length-1);
        return nums;
    }

    public static void quicksort(int[] nums, int start, int end){
        if(start > end) return;
        int i = partition(nums, start, end);
        quicksort(nums, start, i-1);
        quicksort(nums, i+1, end);
    }

    public static int partition(int[] nums, int start, int end){
        int pivot = nums[start];
        int left = start + 1;
        int right = end;
        while (left <= right){
            while (left <= right && nums[left] <= pivot) left ++;
            while (left <= right && nums[right] >= pivot) right --;
            if(left <= right){
                swap(nums, left, right);
            }
        }
        swap(nums, start, right);
        return right;
    }

    public static void swap(int[] nums, int a, int b){
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }

}
